package com.ljx.offer;


/**
 * @author 李捷禧
 * Date: 2023/3/15
 * ClassName: C_22
 */

public class C_22 {
    /**
     * 链表中倒数第k个节点
     * 方式一：
     * 题解：就是双指针方式，都指向头节点，先让一个走k个节点，他们差距就是n - k，
     * 直到第一个指针走到尾节点，第二个就是倒数k个节点开始
     * @param head
     * @param k
     * @return
     */
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode listNode = head,res = head;
        for (int i = 0; i < k; i++) res = res.next;
        while(res != null){
            res = res.next;
            listNode = listNode.next;
        }
        return listNode;
    }

    /**
     * 方式二：
     * 思路一样，内存占用较少
     * @param head
     * @param k
     * @return
     */
    public ListNode getKthFromEnd2(ListNode head, int k) {
        ListNode listNode = head,res = head;
        int num =0;
        while(res != null){
            res = res.next;
           if(num >= k) listNode = listNode.next;
           num++;
        }
        return listNode;
    }

    class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }
}
